package leetcode71_80;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author shhjiang_001
 * @create 2020-06-23 19:13
 */

        /*
        给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
        说明：解集不能包含重复的子集。
        示例:
        输入: nums = [1,2,3]
        输出:
        [
        [3],
        [1],
        [2],
        [1,2,3],
        [1,3],
        [2,3],
        [1,2],
        []
        ]
        */
public class Solution78 {
    List<List<Integer>> resLists = new ArrayList<>();
    public List<List<Integer>> subsets1(int[] nums) {
        Arrays.sort(nums);
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        resLists.add(new ArrayList<>(deque));
        for (int i = 1; i <= nums.length ; i++) {
            method(nums,i,deque);

        }
        return resLists;
    }

    private void method(int[] nums, int k, ArrayDeque<Integer> deque) {
        if (deque.size()== k){
            resLists.add(new ArrayList<>(deque));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (deque.isEmpty() || deque.peek() < nums[i] ){
                deque.push(nums[i]);
                method(nums,k,deque);
                deque.pop();
            }
        }

    }


    public List<List<Integer>> subsets(int[] nums) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        backtrack(nums,0,deque);
        return resLists;
    }

    private void backtrack(int[] nums, int start, ArrayDeque<Integer> deque) {
        resLists.add(new ArrayList<>(deque));
        for (int i = start; i < nums.length; i++) {
            deque.push(nums[i]);
            backtrack(nums,i +1,deque);
            deque.pop();
        }
    }

    @Test
    public void test(){
        subsets(new int[]{1,2,3});
    }
}
